# This is a sample Python script.

# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.
from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        res = list()

        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            l = i + 1
            r = n - 1
            while (l < r):
                if (nums[i] + nums[l] + nums[r] < 0):
                    l += 1
                elif (nums[i] + nums[l] + nums[r] > 0):
                    r -= 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    while (l < r and nums[l] == nums[l + 1]):
                        l += 1
                    while (l < r and nums[r] == nums[r - 1]):
                        r -= 1
                    l += 1
                    r -= 1
        return res


# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    nums = [-1, 0, 1, 2, -1, -4]

    solution = Solution()
    print(solution.threeSum(nums))

# See PyCharm help at https://www.jetbrains.com/help/pycharm/
